const list = [
    {id: 1, parentId: 0, name: 'menu1'},
    {id: 11, parentId: 1, name: 'menu11'},
    {id: 21, parentId: 2, name: 'menu21'},
    {id: 12, parentId: 11, name: 'menu12'},
    {id: 2, parentId: 0, name: 'menu2'},
]

/**
 * 树的算法
 * @params list     待转化数组
 * @params parentId 起始节点
 */
const getTrees = (list, parentId) => {
    if (parentId === undefined) {
        parentId = 0
    }
    let items = {}
    // 获取每个节点的直属子节点，*记住是直属，不是所有子节点
    for (let i = 0; i < list.length; i++) {
        if (list[i].parentId === '' || list[i].parentId === undefined) {
            list[i].parentId = 0
        }
        let key = list[i].parentId
        if (items[key]) {
            items[key].push(list[i])
        } else {
            items[key] = []
            items[key].push(list[i])
        }
    }
    return formatTree(items, parentId)
}

/**
 * 利用递归格式化每个节点
 * @param items
 * @param parentId
 * @param parent
 * @returns {Array}
 */
const formatTree = (items, parentId) => {
    let result = []
    // 递归结束条件
    if (!items[parentId]) {
        return result
    }
    for (let t of items[parentId]) {
        // 递归调用
        t.children = formatTree(items, t.id)
        result.push(t)
    }
    return result
}

/***
 * 广度与优先遍历:简称BFS
 * 注：这个实现方式是非递归实现
 * @param tree
 * @param func
 */
const breadthFirstTraversal = (tree, func) => {
    let node, list = [...tree]
    while (node = list.shift()) {
        func(node)
        node.children && list.push(...node.children)
    }
}

/***
 * 深度优先先序遍历
 * 注：递归方式实现
 * 注：【先序遍历】：又叫先根遍历 根->左子树->右子树
 * @param tree
 * @param fun
 */
const preorderTraversalRecursion = (tree, fun) => {
    tree.forEach(data => {
        fun(data)
        data.children && preorderTraversalRecursion(data.children)
    })
}

/**
 * 深度优先后序遍历
 * 注：递归方式实现
 * 注：【后序遍历】：又叫后根遍历 左子树->右子树->根
 * @param tree
 * @param fun
 */
const postorderTraversalRecursion = (tree, fun) => {
    tree.forEach(data => {
        data.children && preorderTraversalRecursion(data.children)
        fun(data)
    })
}

/***
 * 深度优先先序遍历
 * 注：循环方式实现
 * 注：【先序遍历】：又叫先根遍历 根->左子树->右子树
 * @param tree
 * @param fun
 */
const preorderTraversalCycle = (tree, fun) => {
    let node, list = [...tree]
    while (node = list.shift()) {
        fun(node)
        node.children && list.unshift(...node.children)
    }
}

/**
 * 深度优先后序遍历
 * 注：循环方式实现
 * 注：【后序遍历】：又叫后根遍历 左子树->右子树->根
 * @param tree
 * @param fun
 */
const postorderTraversalCycle = (tree, fun) => {
    let node, list = [...tree], i = 0
    while (node = list[i]) {
        let childCount = node.children ? node.children.length : 0
        if (!childCount || node.children[childCount - 1] === list[i - 1]) {
            fun(node)
            i++
        } else {
            list.splice(i, 0, ...node.children)
        }
    }
}



